#ifndef _TIMER_WHEEL_CPP_
#define _TIMER_WHEEL_CPP_

#include "Timer_Wheel.h"


//Constructor that sets up the timing wheel and also may preallocate some nodes on the free list
template <class TYPE>
Timer_Wheel<TYPE>::Timer_Wheel(unsigned int spoke_count,
												unsigned int resolution,
												size_t prealloc,
												 FreeList* freelist)
: Base (freelist)
 , spokes_ (0)
 , spoke_count_ (0) // calculated in open_i
 , spoke_bits_ (0)
 , res_bits_ (0)
 , earliest_spoke_ (0)
 , iterator_ (0)
 , timer_count_ (0)
{
	this->open_i (prealloc, spoke_count, resolution);
}

template <class TYPE> 
int Timer_Wheel<TYPE>::power2bits (int n,
														int min_bits,
														int max_bits)
{
	int max = (1 << max_bits) - 1;
	if (n > max)
		return max_bits;

	// count the bits in n.
	int i = 0;
	int tmp = n;
	do
	{
		tmp >>= 1;
		++i;
	}
	while (tmp != 0);

	if (i <= min_bits)
		return min_bits;

	// Which is nearest?
	int a = (1 << i) - n;
	int b = (1 << (i - 1)) - n;
	if (b < 0)
		b = -b;
	if (b < a)
		return i - 1;
	return i;
}

/**
* Initialize the queue. Uses the established members for all needed
* information.
*/
template <class TYPE> 
void Timer_Wheel<TYPE>::open_i(size_t prealloc, unsigned int spokes, unsigned int res)
{
	//this->gettimeofday (ACE_OS::gettimeofday);

	// Rather than waste bits in our timer id, we might as well round up
	// the spoke count to the next power of two - 1 . (i.e 1,3,7,15,...127,etc.)
	const int MIN_SPOKE_BITS = 3;  // Allow between 8 and 4096 spokes
	const int MAX_SPOKE_BITS = 12;
	const int MAX_RES_BITS = 20;   // 20 is plenty, even on 64 bit platforms.

	this->spoke_bits_ = power2bits (spokes, MIN_SPOKE_BITS, MAX_SPOKE_BITS);
	this->res_bits_ = power2bits (res, 1, MAX_RES_BITS);

	this->spoke_count_ = 1 << this->spoke_bits_;

	this->free_list_->resize (prealloc + this->spoke_count_);

	this->wheel_time_= (1 << (this->res_bits_ + this->spoke_bits_));

	this->spokes_ = new Timer_Node<TYPE>*[this->spoke_count_];

	// Create the root nodes. These will be treated specially
	for (unsigned int i = 0; i < this->spoke_count_; ++i)
	{
		Timer_Node<TYPE>* root = this->alloc_node ();
		root->set (0, 0, 0, 0, 0, root, root);
		this->spokes_[i] = root;
	}

	iterator_ = new Iterator (*this);
}

/// Destructor just cleans up its memory
template <class TYPE>
Timer_Wheel<TYPE>::~Timer_Wheel (void)
{
	delete iterator_;

	for (unsigned int i = 0; i < this->spoke_count_; ++i)
	{
		// Free all the nodes starting at the root
		Timer_Node<TYPE>* root = this->spokes_[i];
		for (Timer_Node<TYPE>* n = root->get_next (); n != root;)
		{
			Timer_Node<TYPE>* next = n->get_next ();
			n = next;
		}
		delete root;
	}
	delete[] this->spokes_;
}

/// Searches for a node by timer_id within one spoke.
template <class TYPE>
Timer_Node<TYPE>* 
Timer_Wheel<TYPE>::find_spoke_node(unsigned int spoke, long timer_id) const
{
	Timer_Node<TYPE>* root = this->spokes_[spoke];
	for (Timer_Node<TYPE>* n = root->get_next ();
		n != root;
		n = n->get_next ())
	{
		if (n->get_timer_id () == timer_id)
			return n;
	}
	return 0;
}

/// Searches all spokes for a node matching the specified timer_id
/// Uses the spoke encoded in the timer_id as a starting place.
template <class TYPE>
Timer_Node<TYPE>*
Timer_Wheel<TYPE>::find_node (long timer_id) const
{
	if (timer_id == -1)
		return 0;

	// Search the spoke where timer_id was originally scheduled
	unsigned int spoke_mask = this->spoke_count_ - 1;
	unsigned int start = timer_id & spoke_mask;
	Timer_Node<TYPE>* n = this->find_spoke_node (start, timer_id);
	if (n != 0)
		return n;

	// Search the rest of the spokes
	for (unsigned int i = 0; i < this->spoke_count_; ++i)
	{
		if (i != start)
		{ // already searched this one
			n = this->find_spoke_node (i, timer_id);
			if (n != 0)
				return n;
		}
	}

	return 0;
}


// Check to see if the wheel is empty

template <class TYPE> 
int Timer_Wheel<TYPE>::is_empty (void) const
{
	return timer_count_ == 0;
}



// return First (earliest) node in the wheel_'s earliest_spoke_ list
template <class TYPE> 
unsigned long Timer_Wheel<TYPE>::earliest_time (void) const
{
	Timer_Node<TYPE>* n = this->get_first_i ();
	if (n != 0)
		return n->get_timer_value ();
	return 0;
}

/// Uses a simple hash to find which spoke to use based on when the
/// timer is due to expire. Hopefully the 64bit int operations avoid
/// any overflow problems.
template <class TYPE> 
unsigned int 
Timer_Wheel<TYPE>::calculate_spoke(unsigned long expire) const
{
	return static_cast<unsigned int> ((expire >> this->res_bits_) & (this->spoke_count_ - 1));
}

/// Generates a unique timer_id for the given spoke. It should be pretty
/// fast until the point where the counter overflows.  At that time you
/// have to do exhaustive searches within the spoke to ensure that a particular
/// timer id is not already in use. Some optimizations are in place so
/// that this hopefully doesn't have to happen often.
template <class TYPE> 
long Timer_Wheel<TYPE>::generate_timer_id (unsigned int spoke)
{

	int cnt_bits = sizeof (long) * 8 - this->spoke_bits_;
	long max_cnt = ((long)1 << cnt_bits) - 1;
	if (spoke == this->spoke_count_)
		--max_cnt; // Because -1 is used as a special invalid timer_id.

	Timer_Node<TYPE>* root = this->spokes_[spoke];

	if (root == root->get_next ())
		root->set_arg(0);

	long next_cnt = reinterpret_cast<long> (root->get_arg ());

	// This field is used as a counter instead of a timer_id.
	long cnt = root->get_timer_id ();

	if (cnt >= max_cnt && root == root->get_next ())
	{
		// Special case when we overflow on an empty spoke. We can just
		// wrap the count around without searching for duplicates. We only
		// want to do this when the counter overflows, so that we return
		// unique timer_id values as often as possible.
		root->set_timer_id (1);
		return spoke;
	}
	else if (cnt >= max_cnt)
	{ // overflow
		cnt = 0; // try again starting at zero
	}
	else if (next_cnt == 0 || cnt < next_cnt)
	{
		root->set_timer_id (cnt + 1);
		return (cnt << this->spoke_bits_) | spoke;
	}

	// We've run out of consecutive id numbers so now we have to search
	// for a unique id.
	// We'll try increasing numbers until we find one that is not in use,
	// and we'll record the next highest number so that we can avoid this
	// search as often as possible.
	for (; cnt < max_cnt - 1; ++cnt)
	{
		long id = (cnt << this->spoke_bits_) | spoke;
		Timer_Node<TYPE>* n = this->find_spoke_node (spoke, id);
		if (n == 0)
		{
			root->set_timer_id (cnt + 1);
			// Now we need to find the next highest cnt in use
			next_cnt = 0;
			for (; n != root; n = n->get_next ())
			{
				long tmp = n->get_timer_id () >> this->spoke_bits_;
				if (tmp > cnt && (tmp < next_cnt || next_cnt == 0))
					next_cnt = tmp;
			}
			root->set_arg (reinterpret_cast<void*> (next_cnt));
			return id;
		}
	}

	return -1; // We did our best, but the spoke is full.
}

/**
* Creates a Timer_Node based on the input parameters.  Then inserts
* the node into the wheel using reschedule ().  Then returns a timer_id.
*
*  @param type            The data of the timer node
*  @param arg             Asynchronous Completion Token (AKA magic cookie)
*  @param future_time     The time the timer is scheduled for (absolute time)
*  @param interval        If not ACE_Time_Value::zero, then this is a periodic
*                         timer and interval is the time period
*
*  @return Unique identifier (can be used to cancel the timer).
*          -1 on failure.
*/
template <class TYPE> 
long Timer_Wheel<TYPE>::schedule_i (const TYPE& type,
														const void* arg,
														unsigned long future_time,
														unsigned long interval)
{
	Timer_Node<TYPE>* n = this->alloc_node ();

	if (n != 0)
	{
		unsigned int spoke = calculate_spoke (future_time);
		long id = generate_timer_id (spoke);

		if (id != -1)
		{
			n->set (type, arg, future_time, interval, id, 0, 0);
			this->schedule_i (n, spoke, future_time);
		}
		return id;
	}

	return -1;
}


template <class TYPE> 
void Timer_Wheel<TYPE>::reschedule (Timer_Node<TYPE>* n)
{
	unsigned long expire = n->get_timer_value ();
	unsigned int spoke = calculate_spoke (expire);
	this->schedule_i (n, spoke, expire);
}

/// The shared scheduling functionality between schedule() and reschedule()
template <class TYPE> 
void Timer_Wheel<TYPE>::schedule_i(Timer_Node<TYPE>* n,
												unsigned int spoke,
												unsigned long expire)
{
	// See if we need to update the earliest time
	if (this->is_empty() || expire < this->earliest_time ())
		this->earliest_spoke_ = spoke;

	Timer_Node<TYPE>* root = this->spokes_[spoke];
	Timer_Node<TYPE>* last = root->get_prev ();

	++timer_count_;

	// If the spoke is empty
	if (last == root) {
		n->set_prev (root);
		n->set_next (root);
		root->set_prev (n);
		root->set_next (n);
		return;
	}

	// We always want to search backwards from the tail of the list, because
	// this minimizes the search in the extreme case when lots of timers are
	// scheduled for exactly the same time
	Timer_Node<TYPE>* p = root->get_prev ();
	while (p != root && p->get_timer_value () > expire)
		p = p->get_prev ();

	// insert after
	n->set_prev (p);
	n->set_next (p->get_next ());
	p->get_next ()->set_prev (n);
	p->set_next (n);
}


/**
* Find the timer node by using the id as a pointer.  Then use set_interval()
* on the node to update the interval.
*/
template <class TYPE> int
Timer_Wheel<TYPE>::reset_interval (long timer_id,
														unsigned long interval)
{
	Timer_Node<TYPE>* n = this->find_node (timer_id);
	if (n != 0)
	{
		// The interval will take effect the next time this node is expired.
		n->set_interval (interval);
		return 0;
	}
	return -1;
}


/**
* Goes through every list in the wheel and whenever we find one with the
* correct type value, we remove it and continue.  At the end make sure
* we reset the earliest time value in case the earliest timers were
* removed.
*/
template <class TYPE> 
int Timer_Wheel<TYPE>::cancel (const TYPE& type, int skip_close)
{
	int num_canceled = 0; // Note : Technically this can overflow.

	if (!this->is_empty ())
	{
		Timer_Node<TYPE>* first = this->get_first ();
		unsigned long last = first->get_timer_value ();
		int recalc = 0;

		for (unsigned int i = 0; i < this->spoke_count_; ++i)
		{
			Timer_Node<TYPE>* root = this->spokes_[i];
			for (Timer_Node<TYPE>* n = root->get_next (); n != root; )
			{
				if (n->get_type () == type)
				{
					++num_canceled;
					if (n == first)
						recalc = 1;

					Timer_Node<TYPE>* tmp = n;
					n = n->get_next ();

					this->cancel_i (tmp);
				}
				else
				{
					n = n->get_next ();
				}
			}
		}

		if (recalc)
			this->recalc_earliest (last);
	}

	return num_canceled;
}


/**
* Cancels the single timer that is specified by the timer_id.  In this
* case the timer_id is actually a pointer to the node, so we cast it
* to the node.  This can be dangerous if the timer_id is made up
* (or deleted twice) so we do a little sanity check.  Finally we update
* the earliest time in case the earliest timer was removed.
*/
template <class TYPE> 
int Timer_Wheel<TYPE>::cancel (long timer_id,
													const void **arg,
													int skip_close)
{
	Timer_Node<TYPE>* n = this->find_node (timer_id);
	if (n != 0)
	{
		unsigned long last = n->get_timer_value ();

		int recalc = (this->get_first_i () == n);

		if (arg != 0)
			*arg = n->get_arg ();

		this->cancel_i (n);

		if (recalc)
			this->recalc_earliest (last);

		return 1;
	}
	return 0;
}

/// Shared subset of the two cancel() methods.
template <class TYPE> 
void Timer_Wheel<TYPE>::cancel_i (Timer_Node<TYPE>* n)
{
	this->unlink (n);
	this->free_node (n);
}

/// There are a few places where we have to figure out which timer
/// will expire next. This method makes the assumption that spokes
/// are always sorted, and that timers are always in the correct spoke
/// determined from their expiration time.
/// The last time is always passed in, even though you can often calculate
/// it as get_first()->get_timer_value().
template <class TYPE> void
Timer_Wheel<TYPE>::recalc_earliest(unsigned long last)
{
	// This is possible because we use a count for is_empty()
	if (this->is_empty ())
		return;

	unsigned long et = 0;
	unsigned int es = 0;
	unsigned int spoke = this->earliest_spoke_;

	// We will have to go around the wheel at most one time.
	for (unsigned int i = 0; i < this->spoke_count_; ++i)
	{
		Timer_Node<TYPE>* root = this->spokes_[spoke];
		Timer_Node<TYPE>* n = root->get_next ();
		if (n != root)
		{
			ACE_Time_Value t = n->get_timer_value ();
			if (t < last + this->wheel_time_)
			{
				this->earliest_spoke_ = spoke;
				return;
			}
			else if (et == 0 || t < et)
			{
				et = t;
				es = spoke;
			}
		}
		if (++spoke >= this->spoke_count_)
			spoke = 0;
	}

	this->earliest_spoke_ = es;
	//ACE_ERROR((LM_ERROR, "We had to search the whole wheel.\n"));
}


/**
* Removes the earliest node and then find the new <earliest_spoke_>
*/
template <class TYPE> Timer_Node<TYPE> *
Timer_Wheel<TYPE>::remove_first (void)
{
	return remove_first_expired (MAX_TIME);
}

template <class TYPE> void
Timer_Wheel<TYPE>::unlink (Timer_Node<TYPE>* n)
{
	--timer_count_;
	n->get_prev ()->set_next (n->get_next ());
	n->get_next ()->set_prev (n->get_prev ());
	n->set_prev (0);
	n->set_next (0);
}

template <class TYPE> Timer_Node<TYPE> *
Timer_Wheel<TYPE>::remove_first_expired (unsigned long now)
{
	Timer_Node<TYPE>* n = this->get_first ();
	if (n != 0 && n->get_timer_value() <= now)
	{
		this->unlink (n);
		this->recalc_earliest (n->get_timer_value ());
		return n;
	}
	return 0;
}

/**
* Returns the earliest node without removing it
*
* @return The earliest timer node.
*/
template <class TYPE>
Timer_Node<TYPE>*
Timer_Wheel<TYPE>::get_first (void)
{
	return this->get_first_i ();
}

template <class TYPE>
Timer_Node<TYPE>*
Timer_Wheel<TYPE>::get_first_i (void) const
{
	Timer_Node<TYPE>* root = this->spokes_[this->earliest_spoke_];
	Timer_Node<TYPE>* first = root->get_next ();
	if (first != root)
		return first;
	return 0;
}


/**
* @return The iterator
*/
template <class TYPE>
Timer_Queue_Iterator<TYPE>&
Timer_Wheel<TYPE>::iter (void)
{
	this->iterator_->first ();
	return *this->iterator_;
}

/**
* Dummy version of expire to get rid of warnings in Sun CC 4.2
* Just call the expire of the base class.
*/
template <class TYPE> int
Timer_Wheel<TYPE>::expire ()
{
	return Timer_Queue<TYPE>::expire ();
}

/**
* This is a specialized version of expire that is more suited for the
* internal data representation.
*
* @param cur_time The time to expire timers up to.
*
* @return Number of timers expired
*/
template <class TYPE> int
Timer_Wheel<TYPE>::expire (unsigned long cur_time)
{
	int expcount = 0;
	Timer_Node<TYPE>* n = this->remove_first_expired (cur_time);

	while (n != 0)
	{
		bool cancel = true;
		++expcount;

		if (n->get_interval () > 0)
		{
			// Make sure that we skip past values that have already
			// "expired".
			do
			n->set_timer_value (n->get_timer_value () +
				n->get_interval ());
			while (n->get_timer_value () <= cur_time);

			cancel = false;
			this->reschedule (n);
		}

		n->on_timer_out(cur_time);
		if ( cancel )
		{
			n->on_timer_cancel();
			this->free_node (n);
		}
		
		n = this->remove_first_expired (cur_time);
	}

	return expcount;
}

///////////////////////////////////////////////////////////////////////////
// Timer_Wheel_Iterator


template <class TYPE>
Timer_Wheel_Iterator<TYPE>::Timer_Wheel_Iterator
(Wheel& wheel)
: timer_wheel_ (wheel)
{
	this->first();
}


/**
* Destructor, at this level does nothing.
*/
template <class TYPE>
Timer_Wheel_Iterator<TYPE>::~Timer_Wheel_Iterator (void)
{
}


/**
* Positions the iterator at the first position in the timing wheel
* that contains something. spoke_ will be set to the spoke position of
* this entry and current_node_ will point to the first entry in that spoke.
*
* If the wheel is empty, spoke_ will be equal timer_wheel_.spoke_count_ and
* current_node_ would be 0.
*/
template <class TYPE> void
Timer_Wheel_Iterator<TYPE>::first (void)
{
	this->goto_next(0);
}


/**
* Positions the iterator at the next node.
*/
template <class TYPE> void
Timer_Wheel_Iterator<TYPE>::next (void)
{
	if (this->isdone())
		return;

	Timer_Node<TYPE>* n = this->current_node_->get_next ();
	Timer_Node<TYPE>* root = this->timer_wheel_.spokes_[this->spoke_];
	if (n == root)
		this->goto_next (this->spoke_ + 1);
	else
		this->current_node_ = n;
}

/// Helper class for common functionality of next() and first()
template <class TYPE> void
Timer_Wheel_Iterator<TYPE>::goto_next (unsigned int start_spoke)
{
	// Find the first non-empty entry.
	unsigned int sc = this->timer_wheel_.spoke_count_;
	for (unsigned int i = start_spoke; i < sc; ++i)
	{
		Timer_Node<TYPE>* root = this->timer_wheel_.spokes_[i];
		Timer_Node<TYPE>* n = root->get_next ();
		if (n != root)
		{
			this->spoke_ = i;
			this->current_node_ = n;
			return;
		}
	}
	// empty
	this->spoke_ = sc;
	this->current_node_ = 0;
}

/**
* @return True when we there aren't any more items (when current_node_ == 0)
*/
template <class TYPE> int
Timer_Wheel_Iterator<TYPE>::isdone (void) const
{
	return this->current_node_ == 0;
}

/**
* @return The node at the current spokeition in the sequence or 0 if the wheel
*         is empty
*/
template <class TYPE> Timer_Node<TYPE> *
Timer_Wheel_Iterator<TYPE>::item (void)
{
	return this->current_node_;
}

#endif//_TIMER_WHEEL_CPP_